﻿#region copyright info
//------------------------------------------------------------------------------
// <copyright company="ChaosStudio">
//     Copyright (c) 2002-2010 巧思工作室.  All rights reserved.
//     Contact:		MSN:zhouyu@cszi.com , QQ:478779122
//		Link:				http://www.69sea.com http://www.cszi.com
// </copyright>
//------------------------------------------------------------------------------
#endregion
using System;
using System.Collections.Generic;

namespace CS.Caching
{
    /// <summary>
    ///   LRU(最近最少使用)缓存类。
    ///   v:0.1.0
    /// </summary>
    /// 
    /// <description class = "CS.Cache.LRUCache">
    ///   
    /// </description>
    /// 
    /// <history>
    ///   2010-3-22 11:26:27 , zhouyu ,  创建	     
    ///  </history>
    public class LRUCache<TKey, TValue>
    {
        protected LinkedList<TKey> AgeLink;
        protected Dictionary<TKey, CacheDictValue<TKey, TValue>> CacheDict;
        protected int _capacity = -1;
        protected ExpireModeType ExpireMode;
        protected LinkedList<TKey> LRULink;
        protected LinkedList<SampleQueValue> SampleQueue;
        protected int _sampleRate = 2710;
        /// <summary>
        /// 缓存生命周期，单位：秒
        /// </summary>
        protected double Ttl = -1.0;
        /// <summary>
        /// 同步锁
        /// </summary>
        public object SyncRoot;

        /// <summary>
        /// 事件Handler
        /// </summary>
        public event EventHandler<HasErrorEventArgs> HasErrorEvent;

        /// <summary>
        /// 默认：16个缓存
        /// </summary>
        public LRUCache():this(16)
        {
        }

        /// <summary>
        /// 缓存数量构造
        /// </summary>
        /// <param name="capacity">缓存数量</param>
        public LRUCache(int capacity)
        {
            ExpireMode = ExpireModeType.Passive;
            SyncRoot = new object();
            _capacity = (capacity < 0) ? -1 : capacity;
            CacheDict = new Dictionary<TKey, CacheDictValue<TKey, TValue>>();
            SampleQueue = new LinkedList<SampleQueValue>();
            LRULink = new LinkedList<TKey>();
            AgeLink = new LinkedList<TKey>();
        }

        /// <summary>
        /// 缓存数量与过期时间构造
        /// </summary>
        /// <param name="capacity">缓存数量</param>
        /// <param name="lifetime">缓存时间</param>
        public LRUCache(int capacity, double lifetime): this(capacity)
        {
            Ttl = (lifetime < 0.0) ? -1.0 : lifetime;
        }

        /// <summary>
        /// 缓存数量过期时间与过期方式构造
        /// </summary>
        /// <param name="capacity">缓存数量</param>
        /// <param name="lifetime">缓存时间</param>
        /// <param name="expireMode">过期方式</param>
        public LRUCache(int capacity, double lifetime, ExpireModeType expireMode): this(capacity, lifetime)
        {
            ExpireMode = expireMode;
        }

        /// <summary>
        /// 清空缓存
        /// </summary>
        public virtual void Clear()
        {
            CacheDict.Clear();
            LRULink.Clear();
            AgeLink.Clear();
        }

        /// <summary>
        /// 获取命中率
        /// </summary>
        /// <param name="hits"></param>
        /// <param name="total"></param>
        public void GetHitRate(out int hits, out int total)
        {
            hits = SampleQueue.Last.Value.Hits;
            total = SampleQueue.Count;
        }

        /// <summary>
        /// 
        /// </summary>
        protected void HitsInc()
        {
            SampleQueValue sampleQueValue;
            if (SampleQueue.Count < _sampleRate)
            {
                if (SampleQueue.Count == 0)
                {
                    sampleQueValue = new SampleQueValue(1, true);
                    SampleQueue.AddLast(sampleQueValue);
                }
                else
                {
                    sampleQueValue = new SampleQueValue(SampleQueue.Last.Value.Hits + 1, true);
                    SampleQueue.AddLast(sampleQueValue);
                }
            }
            else
            {
                sampleQueValue = SampleQueue.First.Value.IsHit ? new SampleQueValue(SampleQueue.Last.Value.Hits, true) : new SampleQueValue(SampleQueue.Last.Value.Hits + 1, true);

                SampleQueue.RemoveFirst();
                SampleQueue.AddLast(sampleQueValue);
            }

        }

        /// <summary>
        /// 是否过期
        /// </summary>
        /// <param name="cacheDictValue"></param>
        /// <param name="nowTime"></param>
        /// <returns></returns>
        protected bool IsExpired(CacheDictValue<TKey, TValue> cacheDictValue, DateTime nowTime)
        {
            return ((Ttl >= 0.0) && (cacheDictValue.CreateTime.AddSeconds(Ttl) <= nowTime));
        }

        protected void MissesInc()
        {

            SampleQueValue value2;
            if (SampleQueue.Count < _sampleRate)
            {
                if (SampleQueue.Count == 0)
                {
                    value2 = new SampleQueValue(0, false);
                    SampleQueue.AddLast(value2);
                }
                else
                {
                    value2 = new SampleQueValue(SampleQueue.Last.Value.Hits, false);
                    SampleQueue.AddLast(value2);
                }
            }
            else
            {
                value2 = SampleQueue.First.Value.IsHit ? new SampleQueValue(SampleQueue.Last.Value.Hits - 1, false) : new SampleQueValue(SampleQueue.Last.Value.Hits, false);

                SampleQueue.RemoveFirst();
                SampleQueue.AddLast(value2);
            }

        }

        private void OnHasError(HasErrorEventArgs e)
        {
            var hasErrorEvent = HasErrorEvent;
            if (hasErrorEvent != null)
            {
                hasErrorEvent(this, e);
            }
        }

        public bool Put(TKey key, TValue value)
        {
            TValue local;
            return Put(key, value, out local);
        }

        public virtual bool Put(TKey key, TValue value, out TValue oldValue)
        {
            CacheDictValue<TKey, TValue> value2;
            bool flag3;
            oldValue = default(TValue);
            if (ExpireMode == ExpireModeType.Active)
            {
                RemoveAllExpired();
            }

            Label_028D:
            flag3 = true;
            bool flag = this.CacheDict.TryGetValue(key, out value2);
            if (flag)
            {
                oldValue = value2.Value;
                this.LRULink.Remove(value2.LruLinkNode);
                this.AgeLink.Remove(value2.AgeLinkNode);
                value2.Value = value;
                value2.UpdateCreateTime();
                this.LRULink.AddFirst(value2.LruLinkNode);
                this.AgeLink.AddFirst(value2.AgeLinkNode);
            }
            else
            {
                LinkedListNode<TKey> node;
                OutOfMemoryException exception;
                LinkedListNode<TKey> node2;
                if (this._capacity >= 0)
                {
                    while ((this.CacheDict.Count > 0) && (this.CacheDict.Count >= this._capacity))
                    {
                        this.RemoveLRU();
                    }
                }
                try
                {
                    node = this.LRULink.AddFirst(key);
                }
                catch (OutOfMemoryException exception1)
                {
                    exception = exception1;
                    this.OnHasError(new HasErrorEventArgs(exception, CacheDict.Count));
                    if (!this.RemoveLRU())
                    {
                        throw;
                    }
                    this._capacity = this.CacheDict.Count + 1;
                    goto Label_028D;
                }
                try
                {
                    node2 = this.AgeLink.AddFirst(key);
                }
                catch (OutOfMemoryException exception2)
                {
                    exception = exception2;
                    this.OnHasError(new HasErrorEventArgs(exception, this.CacheDict.Count));
                    node = null;
                    this.LRULink.RemoveFirst();
                    if (!this.RemoveLRU())
                    {
                        throw;
                    }
                    this._capacity = this.CacheDict.Count + 1;
                    goto Label_028D;
                }
                try
                {
                    value2 = new CacheDictValue<TKey, TValue>(value, node, node2);
                }
                catch (OutOfMemoryException exception3)
                {
                    exception = exception3;
                    this.OnHasError(new HasErrorEventArgs(exception, this.CacheDict.Count));
                    node = null;
                    this.LRULink.RemoveFirst();
                    node2 = null;
                    this.AgeLink.RemoveFirst();
                    if (!this.RemoveLRU())
                    {
                        throw;
                    }
                    this._capacity = this.CacheDict.Count + 1;
                    goto Label_028D;
                }
                try
                {
                    this.CacheDict.Add(key, value2);
                }
                catch (OutOfMemoryException exception4)
                {
                    exception = exception4;
                    this.OnHasError(new HasErrorEventArgs(exception, this.CacheDict.Count));
                    node = null;
                    this.LRULink.RemoveFirst();
                    node2 = null;
                    this.AgeLink.RemoveFirst();
                    value2 = null;
                    if (!this.RemoveLRU())
                    {
                        throw;
                    }
                    this._capacity = this.CacheDict.Count + 1;
                    goto Label_028D;
                }
            }
            return !flag;
        }

        /// <summary>
        /// 移除缓存
        /// </summary>
        /// <param name="key">健</param>
        /// <returns></returns>
        public bool Remove(TKey key)
        {
            TValue local;
            return Remove(key, out local);
        }

        /// <summary>
        /// 移去缓存
        /// </summary>
        /// <param name="key">键</param>
        /// <param name="value">值：输出</param>
        /// <returns></returns>
        public virtual bool Remove(TKey key, out TValue value)
        {
            CacheDictValue<TKey, TValue> cacheDictValue;
            value = default(TValue);
            if (ExpireMode == ExpireModeType.Active)
            {
                RemoveAllExpired();     //主动方式时释放所有过期的
            }
            if (!CacheDict.TryGetValue(key, out cacheDictValue))
            {
                return false;     //该缓存不存在
            }
            LRULink.Remove(cacheDictValue.LruLinkNode);
            AgeLink.Remove(cacheDictValue.AgeLinkNode);
            CacheDict.Remove(key);
            value = cacheDictValue.Value;
            return true;
        }

        protected virtual void RemoveAllExpired()
        {
            var now = DateTime.Now;
            if (Ttl >= 0.0)
            {
                LinkedListNode<TKey> last = this.AgeLink.Last;
                while (last != null)
                {
                    CacheDictValue<TKey, TValue> cacheDictValue = this.CacheDict[last.Value];
                    if (this.IsExpired(cacheDictValue, now))
                    {
                        this.CacheDict.Remove(last.Value);
                        this.LRULink.Remove(cacheDictValue.LruLinkNode);
                        this.AgeLink.Remove(cacheDictValue.AgeLinkNode);
                        last = last.Previous;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        protected bool RemoveLRU()
        {
            TValue local;
            return this.RemoveLRU(out local);
        }

        protected virtual bool RemoveLRU(out TValue value)
        {
            value = default(TValue);
            LinkedListNode<TKey> last = this.LRULink.Last;
            if (last == null)
            {
                return false;
            }
            CacheDictValue<TKey, TValue> value2 = this.CacheDict[last.Value];
            value = value2.Value;
            this.CacheDict.Remove(last.Value);
            this.LRULink.RemoveLast();
            this.AgeLink.Remove(value2.AgeLinkNode);
            return true;
        }

        public virtual bool TryGet(TKey key, out TValue value)
        {
            CacheDictValue<TKey, TValue> value2;
            value = default(TValue);
            if (this.ExpireMode == ExpireModeType.Active)
            {
                this.RemoveAllExpired();
            }
            if (!this.CacheDict.TryGetValue(key, out value2))
            {
                this.MissesInc();
                return false;
            }
            if (this.IsExpired(value2, DateTime.Now))
            {
                this.CacheDict.Remove(key);
                this.LRULink.Remove(value2.LruLinkNode);
                this.AgeLink.Remove(value2.AgeLinkNode);
                this.MissesInc();
                return false;
            }
            value2.UpdateAccessTime();
            this.LRULink.Remove(value2.LruLinkNode);
            this.LRULink.AddFirst(value2.LruLinkNode);
            this.HitsInc();
            value = value2.Value;
            return true;
        }

        // Properties
        public int Capacity
        {
            get{return _capacity;}
            set
            {
                _capacity = (value < 0) ? -1 : value;
                while (CacheDict.Count > _capacity)
                {
                    RemoveLRU();
                }
            }
        }

        public int Count
        {
            get { return CacheDict.Count; }
        }

        /// <summary>
        /// 当前缓存实例的过期方式
        /// </summary>
        public ExpireModeType CurrExpireMode
        {
            get{return ExpireMode;}
            set{ExpireMode = value;}
        }

        public double Lifetime
        {
            get{return Ttl;}
            set{Ttl = (value < 0.0) ? -1.0 : value;}
        }

        public int SampleRate
        {
            get{return _sampleRate;}
            set{_sampleRate = (value <= 0) ? 1 : value;}
        }


        /// <summary>
        /// 缓存字典
        /// </summary>
        /// <typeparam name="TKeyNode">键节点</typeparam>
        /// <typeparam name="TValueNode">值节点</typeparam>
        protected class CacheDictValue<TKeyNode, TValueNode>
        {
            // Fields
            private readonly LinkedListNode<TKeyNode> ageLinkNode;
            private readonly LinkedListNode<TKeyNode> lruLinkNode;
            public TValueNode Value;

            /// <summary>
            /// 构造
            /// </summary>
            /// <param name="value"></param>
            /// <param name="lruLinkNode"></param>
            /// <param name="ageLinkNode"></param>
            public CacheDictValue(TValueNode value, LinkedListNode<TKeyNode> lruLinkNode, LinkedListNode<TKeyNode> ageLinkNode)
            {
                Value = value;
                this.lruLinkNode = lruLinkNode;
                this.ageLinkNode = ageLinkNode;
                CreateTime = DateTime.Now;
                AccessTime = CreateTime;
            }

            /// <summary>
            /// 更新访问时间
            /// </summary>
            public void UpdateAccessTime()
            {
                AccessTime = DateTime.Now;
            }

            /// <summary>
            /// 更新创建时间
            /// </summary>
            public void UpdateCreateTime()
            {
                CreateTime = DateTime.Now;
                AccessTime = CreateTime;
            }

            /// <summary>
            /// 访问时间
            /// </summary>
            public DateTime AccessTime { get; private set; }

            public LinkedListNode<TKeyNode> AgeLinkNode
            {
                get { return ageLinkNode; }
            }

            /// <summary>
            /// 创建时间
            /// </summary>
            public DateTime CreateTime { get; private set; }

            public LinkedListNode<TKeyNode> LruLinkNode
            {
                get { return lruLinkNode; }
            }

        }
     
    }
}